#ifndef __HASHMAP_GENERIC_H__
#define __HASHMAP_GENERIC_H__

namespace inf {
    /*
    ============
    hash policies
    ============
    */

    /*
    ============
    HashGeneratorDefault
    ============
    */
    struct HashGeneratorDefault {
        template< class type >
        static int hash( const HashIndex& hasher, const type& value ) {
            return hasher.generate_key( value );
        }
    };

    /*
    ============
    HashGeneratorNumeric
    ============
    */
    struct HashGeneratorNumeric {
        template< class type >
        static int hash( const HashIndex& hasher, const type& value ) {
            return hasher.generate_key( value, 0 );
        }
    };

    /*
    ============
    HashGeneratorIHash
    case-insensitive string hash
    ============
    */
    struct HashGeneratorIHash {
        template< class type >
        static int hash( const HashIndex& hasher, const type& value ) {
            return hasher.generate_key( value, false );
        }
    };


    /*
    ============
    Key comparison policies
    ============
    */

    /*
    ============
    HashCompareDefault
    ============
    */
    struct HashCompareDefault {
        template< class type1, class type2 >
        static bool compare( const type1& lhs, const type2& rhs ) {
            return lhs == rhs;
        }
    };


    /*
    ============
    HashCompareStrCmp
    ============
    */
    struct HashCompareStrCmp {
        template< class type1, class type2 >
        static bool compare( const type1& lhs, const type2& rhs ) {
            return Str::cmp( lhs, rhs ) == 0;
        }
    };


    /*
    ============
    HashCompareStrIcmp
    ============
    */
    struct HashCompareStrIcmp {
        template< class type1, class type2 >
        static bool compare( const type1& lhs, const type2& rhs ) {
            return Str::cmp( lhs, rhs, false ) == 0;
        }
    };

    /*
    ============
    HashMapGeneric
    allow for generic mapping between arbitrary data types
    ============
    */
    template<
        class key,
        class type, 
        class hashCompare = HashCompareDefault,
        class hashGenerator = HashGeneratorDefault,
        class hashIndexType = HashIndex
    >
    class HashMapGeneric {
    public:
        typedef Pair< key, type >			HMPair;
        typedef const HMPair				const_pair;

        typedef HMPair*						iterator;
        typedef const HMPair* 				const_iterator;

        typedef type						value_type;
        typedef const type					const_value_type;
        typedef const key					const_key;

        // < location of insertion, true if the item is new, false if the item already existed >
        typedef Pair< iterator, bool >	    insert_result;

        typedef	hashGenerator				hash_generator;
        typedef hashCompare					hash_compare;

        HashMapGeneric( const HashMapGeneric& rhs );
        explicit							HashMapGeneric( int granularity = 16 );
        HashMapGeneric&						operator=( const HashMapGeneric& rhs );

        void								set_granularity( int newGranularity );
        void								init_hash( const int newHashSize, const int newIndexSize );

        size_t								total_size( void ) const;

        // if the key-value mapping already exists, the value is merely reassigned
        // the bool parameter of insert_result reports the results: it is true if
        // the item needed to be added, false if it already existed
        insert_result						set( const key& key_, const type& value );

        // this is a convenience accessor equivalent to set
        // this is slightly more expensive than using set directly in the case of new item insertions
        type&								operator[]( const key& key_ );

        iterator							find_index( int index );
        const_iterator						find_index( int index ) const;

        void								clear();

        bool								remove( const key& key_ );

        // Information
        int									size() const;
        bool								empty() const;

        // Iteration
        iterator							begin();
        iterator							end();

        const_iterator						begin() const;
        const_iterator						end() const;

        void								remove( iterator iter );

        int									count( const key& key_ ) const;

        void								delete_keys();
        void								delete_values();

        void								swap( HashMapGeneric& rhs );

        // These various find version are templates so that in certain cases (mainly string mappings)
        // we can avoid constructing a temporary of type key
        template< class OtherKey >
        iterator							find( const OtherKey& key_ ) {
            int hashKey = hash_generator::hash( hash, key_ );
            for( int i = hash.get_first( hashKey ); i != HashIndex::NULL_INDEX; i = hash.get_next( i ) ) {
                if( hash_compare::compare( pairs[ i ].first, key_ )) {
                    return &pairs[ i ];
                }
            }

            return end();
        }
        template< class OtherKey >
        const_iterator							find( const OtherKey& key_ ) const {
            int hashKey = hash_generator::hash( hash, key_ );
            for( int i = hash.get_first( hashKey ); i != HashIndex::NULL_INDEX; i = hash.get_next( i ) ) {
                if( hash_compare::compare( pairs[ i ].first, key_ )) {
                    return &pairs[ i ];
                }
            }

            return end();
        }

    private:
        insert_result						set_new_item( const key& key_, const type& value );

    private:
        typedef List< HMPair > PairList;

        hashIndexType 	hash;
        PairList		pairs;
    };

#define HASHMAP_TEMPLATE_HEADER template< class key, class type, class hashCompare, class hashGenerator, class hashIndexType >
#define HASHMAP_TEMPLATE_TAG HashMapGeneric< key, type, hashCompare, hashGenerator, hashIndexType >

    /*
    ============
    HASHMAP_TEMPLATE_TAG::HashMapGeneric
    ============
    */

    HASHMAP_TEMPLATE_HEADER 
        HASHMAP_TEMPLATE_TAG::HashMapGeneric( int granularity ) {
            set_granularity( granularity );
    }

    /*
    ============
    HASHMAP_TEMPLATE_TAG::HashMapGeneric
    ============
    */
    HASHMAP_TEMPLATE_HEADER
        HASHMAP_TEMPLATE_TAG::HashMapGeneric( const HashMapGeneric& rhs ) {
            *this = rhs;
    }

    /*
    ============
    HASHMAP_TEMPLATE_TAG::HashMapGeneric
    ============
    */
    HASHMAP_TEMPLATE_HEADER
        size_t HASHMAP_TEMPLATE_TAG::total_size( void ) const {
            return sizeof( *this ) + hash.total_size() + pairs.total_size();
    }

    /*
    ============
    HASHMAP_TEMPLATE_TAG::operator
    ============
    */
    HASHMAP_TEMPLATE_HEADER
        HASHMAP_TEMPLATE_TAG& HASHMAP_TEMPLATE_TAG::operator=( const HashMapGeneric& rhs ) {
            if( this != &rhs ) {
                pairs = rhs.pairs;
                hash = rhs.hash;
            }
            return *this;
    }

    /*
    ============
    HASHMAP_TEMPLATE_TAG::size
    ============
    */
    HASHMAP_TEMPLATE_HEADER
        int HASHMAP_TEMPLATE_TAG::size() const {
            return pairs.size();
    }

    /*
    ============
    HASHMAP_TEMPLATE_TAG::empty
    ============
    */
    HASHMAP_TEMPLATE_HEADER
        bool HASHMAP_TEMPLATE_TAG::empty() const {
            return size() == 0;
    }

    /*
    ============
    HASHMAP_TEMPLATE_TAG::begin
    ============
    */
    HASHMAP_TEMPLATE_HEADER
        typename HASHMAP_TEMPLATE_TAG::iterator HASHMAP_TEMPLATE_TAG::begin() {
            return pairs.begin();	
    }

    /*
    ============
    HASHMAP_TEMPLATE_TAG::begin
    ============
    */
    HASHMAP_TEMPLATE_HEADER
        typename HASHMAP_TEMPLATE_TAG::const_iterator HASHMAP_TEMPLATE_TAG::begin() const {
            return pairs.begin();
    }

    /*
    ============
    HASHMAP_TEMPLATE_TAG::end
    ============
    */
    HASHMAP_TEMPLATE_HEADER
        typename HASHMAP_TEMPLATE_TAG::iterator HASHMAP_TEMPLATE_TAG::end() {
            return pairs.end();
    }

    /*
    ============
    HASHMAP_TEMPLATE_TAG::end
    ============
    */
    HASHMAP_TEMPLATE_HEADER
        typename HASHMAP_TEMPLATE_TAG::const_iterator HASHMAP_TEMPLATE_TAG::end() const {
            return pairs.end();
    }

    /*
    ============
    HASHMAP_TEMPLATE_TAG::set
    ============
    */
    HASHMAP_TEMPLATE_HEADER
        typename HASHMAP_TEMPLATE_TAG::insert_result HASHMAP_TEMPLATE_TAG::set( const key& key_, const type& value ) {	
            iterator result = find( key_ );
            if( result != end() ) {
                result->second = value;
                return insert_result( result, false );
            }

            return set_new_item( key_, value );
    }

    /*
    ============
    HASHMAP_TEMPLATE_TAG::set_new_item
    ============
    */
    HASHMAP_TEMPLATE_HEADER
        typename HASHMAP_TEMPLATE_TAG::insert_result HASHMAP_TEMPLATE_TAG::set_new_item( const key& key_, const type& value ) {	
            assert( find( key_ ) == end() );
            int hashKey = hash_generator::hash( hash, key_ );
            iterator result = &pairs.alloc_to_back();
            result->first = key_;
            result->second = value;

            hash.add( hashKey,  pairs.size() - 1 );
            return insert_result( result, true );
    }

    /*
    ============
    HASHMAP_TEMPLATE_TAG::set_granularity
    ============
    */
    HASHMAP_TEMPLATE_HEADER
        void HASHMAP_TEMPLATE_TAG::set_granularity( int newGranularity ) {
            pairs.set_granularity( newGranularity );
            hash.set_granularity( newGranularity );
    }

    /*
    ============
    HASHMAP_TEMPLATE_TAG::init_hash
    ============
    */
    HASHMAP_TEMPLATE_HEADER
        void HASHMAP_TEMPLATE_TAG::init_hash( const int newHashSize, const int newIndexSize ) {
            hash.init( newHashSize, newIndexSize );
    }

    /*
    ============
    HASHMAP_TEMPLATE_TAG::find_index
    ============
    */
    HASHMAP_TEMPLATE_HEADER
        typename HASHMAP_TEMPLATE_TAG::iterator HASHMAP_TEMPLATE_TAG::find_index( int index ) {
            return &pairs[ index ];
    }

    /*
    ============
    HASHMAP_TEMPLATE_TAG::find_index
    ============
    */
    HASHMAP_TEMPLATE_HEADER
        typename HASHMAP_TEMPLATE_TAG::const_iterator HASHMAP_TEMPLATE_TAG::find_index( int index ) const {
            return &pairs[ index ];
    }

    /*
    ============
    HASHMAP_TEMPLATE_TAG::clear
    ============
    */
    HASHMAP_TEMPLATE_HEADER
        void HASHMAP_TEMPLATE_TAG::clear() {
            pairs.clear();
            hash.clear();
    }

    /*
    ============
    HASHMAP_TEMPLATE_TAG::remove
    ============
    */
    HASHMAP_TEMPLATE_HEADER
        bool HASHMAP_TEMPLATE_TAG::remove( const key& key_ ) {
            int hashKey = hash_generator::hash( hash, key_ );		
            for( int i = hash.get_first( hashKey ); i != HashIndex::NULL_INDEX; i = hash.get_next( i ) ) {
                if( hash_compare::compare( pairs[ i ].first, key_ )) {
                    hash.remove_index( hashKey, i );
                    pairs.remove_index( i );
                    return true;
                }
            }
            return false;
    }

    /*
    ============
    HASHMAP_TEMPLATE_TAG::operator[]
    ============
    */
    HASHMAP_TEMPLATE_HEADER
        type&	HASHMAP_TEMPLATE_TAG::operator[]( const key& key_ ) {
            iterator iter = find( key_ );
            if( iter != end() ) {
                return iter->second;
            }

            insert_result result = set_new_item( key_, type() );
            return result.first->second;
    }

    /*
    ============
    HASHMAP_TEMPLATE_TAG::remove
    ============
    */
    HASHMAP_TEMPLATE_HEADER
        void HASHMAP_TEMPLATE_TAG::remove( iterator iter ) {
            remove( iter->first );
    }

    /*
    ============
    HASHMAP_TEMPLATE_TAG::count
    ============
    */
    HASHMAP_TEMPLATE_HEADER
        int HASHMAP_TEMPLATE_TAG::count( const key& key_ ) const {
            int hashKey = hash_generator::hash( hash, key_ );

            int count = 0;
            for( int i = hash.get_first( hashKey ); i != HashIndex::NULL_INDEX; i = hash.get_next( i ) ) {
                count++;
            }
            return count;
    }

    /*
    ============
    HASHMAP_TEMPLATE_TAG::delete_keys
    ============
    */
    HASHMAP_TEMPLATE_HEADER
        void HASHMAP_TEMPLATE_TAG::delete_keys() {
            for( int i = 0; i < pairs.size(); i++ ) {
                delete pairs[ i ].first;
            }
    }

    /*
    ============
    HASHMAP_TEMPLATE_TAG::delete_values
    ============
    */
    HASHMAP_TEMPLATE_HEADER
        void HASHMAP_TEMPLATE_TAG::delete_values() {
            for( int i = 0; i < pairs.size(); i++ ) {
                delete pairs[ i ].second;
            }
    }

    /*
    ============
    HASHMAP_TEMPLATE_TAG::delete_values
    ============
    */
    HASHMAP_TEMPLATE_HEADER
        void HASHMAP_TEMPLATE_TAG::swap( HashMapGeneric& rhs ) {
            pairs.swap( rhs.pairs );
            hash.swap( rhs.hash );
    }

}   // ::inf

#undef HASHMAP_TEMPLATE_HEADER
#undef HASHMAP_TEMPLATE_TAG

#endif // !__HASHMAP_GENERIC_H__
